package 堆排序;

import java.util.Arrays;

public class 堆排序 {
    public static void  adjustDown(int[] arr,int root,int len) {
        int parent=root;
        int child=2*parent+1;

        while (child<len) {
            if (child+1<len && arr[child]<arr[child+1]) {
                child++;
            }
            //保证 child 当前指向左右孩子值最大的那一个节点
            if (arr[parent]<arr[child]) {
                int tmp=arr[parent];
                arr[parent]=arr[child];
                arr[child]=tmp;

                //往下判断以 孩子节点为根节点的子树
                parent=child;
                child=parent*2+1;
            }else {
                break;//当前子树不需要调整，结束循环，调整下一棵树
            }
        }
    }

    public static void createHeap(int[] arr) {

        //建大堆
        //从 最后一棵子树的根节点 开始向下调整建堆
        for (int i = (arr.length-1-1)/2; i >=0; i--) {
            //传入当前子树的根节点，开始向下调整
            adjustDown(arr,i,arr.length);
        }
    }

    public static void heapSort(int[] arr) {//堆排序：从小到大，建大堆
        createHeap(arr);//构建大堆 O(n)

        int end=arr.length-1;//从堆的最后一个节点开始
        while (end>0) {  //O(n)
            int tmp=arr[end];
            arr[end]=arr[0];
            arr[0]=tmp;
            adjustDown(arr,0,end);//重新调整，构建新的大堆   O(n*logn)
            end--;
        }

    }

    public static void main(String[] args) {
        int[] arr={12,5,9,34,6,8,33,56,89,0,7,4,22,55,77};
        heapSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}
